package com.zhaofan.other;

/**
 * https://leetcode-cn.com/problems/container-with-most-water/
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 */
public class No11 {
    public static void main(String[] args) {
        int[] a={1,8,6,2,5,4,8,3,7};
//        int[] a={1,2,1};
        No11 no = new No11();

        System.out.println(no.maxArea2(a));
    }

    /**
     * 枚举所有值，超时
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        if(height.length<=1) return 0;
        int max=0;
        for (int i = 0; i < height.length; i++) {
            for (int j=i+1;j<height.length;j++){
                int width=j-i;
                int area=Math.min(height[i],height[j])*width;
                if(max<area) max=area;
            }
        }
        return max;
    }

    /**
     * 双指针法，
     */
    public int maxArea2(int[] height) {
        if(height.length<=1) return 0;
        int max=0,left=0,right=height.length-1;
        while(left<right){
            int width=right-left;
            int area=Math.min(height[left],height[right])*width;
            if(max<area) max=area;
            if(height[left]>height[right]) --right;
            else ++left;
        }
        return max;
    }
}
